/**
 * 
 */
package dp.passed;

import java.math.BigInteger;

/**
 * @author xyyi
 *
 */
public class DistinctSubsequences {

	/**
	Given a string S and a string T, count the number of distinct of T in S as subsequences.

	A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

	Here is an example:
	S = "rabbbit", T = "rabbit"

	Return 3.
	
	dp[si][ji]  the number of distinct subsequences of T[0...ti] in S[0..si]
	 */
	public int numDistinct(String S, String T) {
		if (S.length() < T.length())
			return 0;

		int[][] dp = new int[S.length() + 1][T.length() + 1];
		for (int ti = 1; ti <= T.length(); ti++) {
			dp[0][ti] = 0;
		}
		for (int si = 0; si <= S.length(); si++) {
			dp[si][0] = 1;
		}

		for (int si = 1; si <= S.length(); si++) {
			for (int ti = 1; ti <= T.length(); ti++) {
				dp[si][ti] = dp[si - 1][ti];
				if (S.charAt(si - 1) == T.charAt(ti - 1)) {
					dp[si][ti] += dp[si - 1][ti - 1];
				}
			}
		}

		return dp[S.length()][T.length()];
	}

	/**
		dp[si][ji]  the number of distinct subsequences of T[0...ti) in S[0..si])
		if T[ti - 1] == S[si - 1]
		dp[si][ti] = dp[si - 1][ti - 1]
		if we do not want to use it
		dp[si][ti] = dp[si - 1][ti];
	 */
	public int numDistinctSpace(String S, String T) {
		int[] dp = new int[T.length() + 1];
		dp[0] = 1;

		for (int si = 0; si < S.length(); si++) {
			for (int ti = T.length() - 1; ti >= 0; ti--) {
				dp[ti + 1] += S.charAt(si) == T.charAt(ti) ? dp[ti] : 0;
			}
		}

		return dp[T.length()];
	}

	/**Let f(i, j) to be the number of distinct subsequences of T(j:) in S(i:). Consider the ith character in S. If we can use it to match T[j], namely S[i] == T[j], then

	f(i, j) = f(i+1, j+1).

	If we do not want use it in our matching, then

	f(i, j) = f(i+1, j).

	Thus,f(i, j) = f(i+1, j) + (S[i] == T[j]) * f(i+1, j+1).

	It is very much the same as how we solve C(n, m) or the knapsack problem.
	 */
	public int numDistinctSpace1(String S, String T) {
		int dp[] = new int[T.length() + 1];
		dp[T.length()] = 1;
		for (int si = S.length() - 1; si >= 0; si--) {
			for (int ti = 0; ti < T.length(); ti++) {
				dp[ti] += S.charAt(si) == T.charAt(ti) ? dp[ti + 1] : 0;
			}
		}
		return dp[0];
	}

	public BigInteger numDistinctBigInt(String S, String T) {
		if (S.length() < T.length())
			return BigInteger.valueOf(0);

		BigInteger[][] dp = new BigInteger[S.length() + 1][T.length() + 1];
		for (int ti = 1; ti <= T.length(); ti++) {
			dp[0][ti] = BigInteger.valueOf(0);
		}
		for (int si = 0; si <= S.length(); si++) {
			dp[si][0] = BigInteger.valueOf(1);

		}

		for (int si = 1; si <= S.length(); si++) {
			for (int ti = 1; ti <= T.length(); ti++) {
				dp[si][ti] = dp[si - 1][ti];
				if (S.charAt(si - 1) == T.charAt(ti - 1)) {
					dp[si][ti] = dp[si][ti].add(dp[si - 1][ti - 1]);
				}
			}
		}

		return dp[S.length()][T.length()];
	}

	/**
	 * 
	 */
	public DistinctSubsequences() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
